#include "leftistHeap.h"
#include "logger.h"

static void SwapChildren(PriorityQueue H1)
{
    PriorityQueue Tmp = H1->Left;
    H1->Left = H1->Right;
    H1->Right = Tmp;
}

static PriorityQueue Merge1(PriorityQueue H1, PriorityQueue H2)
{
    if (H1->Left == NULL)
        H1->Left = H2;
    else
    {
        H1->Right = Merge(H1->Right, H2);
        if (H1->Left->Npl < H1->Right->Npl)
            SwapChildren(H1);
        H1->Npl = H1->Right->Npl + 1;
    }
    return H1;
}

PriorityQueue Merge(PriorityQueue H1, PriorityQueue H2)
{
    if (H1 == NULL)
        return H2;
    if (H2 == NULL)
        return H1;
    if (H1->Element < H2->Element)
        return Merge1(H1, H2);
    else
        return Merge1(H2, H1);
}

PriorityQueue Insert1(ElementType X, PriorityQueue H)
{
    PriorityQueue SingleNode;
    SingleNode = malloc(sizeof(*SingleNode));
    if (!SingleNode)
        FatalError("Out of space");
    else
    {
        SingleNode->Element = X;
        SingleNode->Left = SingleNode->Right = NULL;
        SingleNode->Npl = 0;
        H = Merge(H, SingleNode);
    }
    return H;
}

int IsEmpty(PriorityQueue H)
{
    return H == NULL;
}

PriorityQueue Delete1(PriorityQueue H)
{
    PriorityQueue LeftHeap, RightHeap;
    if (IsEmpty(H))
        FatalError("Heap is empty");
    LeftHeap = H->Left;
    RightHeap = H->Right;
    free(H);
    Merge(LeftHeap, RightHeap);
}